package algorithms.leaning.class23;

import common.util.MyUtil;

/**
 * 给定一个正数数组arr，
 * 请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近
 * 返回：
 * 最接近的情况下，较小集合的累加和
 *
 * @author guichang
 * @date 2021/6/25
 */

@SuppressWarnings("all")
public class Code1_动态规划_累加和最接近 {
    // 累加和小于等于总和的一半

    public static void main(String[] args) {
        //int[] nums = MyUtil.createRandomArray(10, 1, 20);
        int[] nums = MyUtil.createArray(1, 10, 5, 20);
        MyUtil.print(minSum(nums));
        MyUtil.print(minSumDp(nums));
    }

    public static int minSum(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        return process(nums, 0, sum / 2);
    }

    /**
     * 当前来到了index位置，累加和<=rest的最小累加和是多少
     */
    private static int process(int[] nums, int index, int rest) {
        if (index == nums.length) {
            return 0;
        }
        int p1 = process(nums, index + 1, rest);
        int p2 = 0;
        if (rest - nums[index] >= 0) {
            p2 = nums[index] + process(nums, index + 1, rest - nums[index]);
        }
        return Math.max(p1, p2);
    }

    public static int minSumDp(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        sum /= 2;
        int N = nums.length;
        int[][] dp = new int[N + 1][sum + 1];
        // 整体从下往上，内部从左往右
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= sum; rest++) {
                int p1 = dp[index + 1][rest];
                int p2 = 0;
                if (rest - nums[index] >= 0) {
                    p2 = nums[index] + dp[index + 1][rest - nums[index]];
                }
                dp[index][rest] = Math.max(p1, p2);
            }
        }
        return dp[0][sum];
    }


}